package arithmetic1.dynamicPlanning;

/*
    动态规划解决0-1背包问题：
        v[0][j]=v[i][0]=0;
        当w[i]>j时:v[i][j]=v[i-1][j]
        当w[i]<j时:v[i][j]=max{v[i-1][j],v[i]+v[i-1][j-w[i]]}
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        //定义物品重量
        int w[]={1,2,3};
        //物品价值
        int val[]={1000,1500,2000};
        //背包最大容量
        int j=4;
        //保存每次的数据，行为物品数量+1，列为背包容量+1
        int v[][]=new int[w.length+1][j+1];
        //保存分配的方法
        int path[][]=new int[w.length+1][j+1];

        for(int c=1;c<=j;c++){      //c代表背包总重量
            for(int r=1;r<=w.length;r++){   //r代表当前物品的个数
                if(w[r-1]>c){ //当前物品重量大于背包总重量
                    v[r][c]=v[r-1][c];
                }else{
//                    v[r][c]=Math.max(v[r-1][c],val[r-1]+v[r-1][c-w[r-1]]);
                    if(v[r-1][c]<val[r-1]+v[r-1][c-w[r-1]]){
                        v[r][c]=val[r-1]+v[r-1][c-w[r-1]];
                        path[r][c]=1;
                    }else {
                        v[r][c]=v[r-1][c];
                    }
                }
            }
        }
        for(int arr[]:v){
            for(int value:arr){
                System.out.print(value+"\t\t");
            }
            System.out.println();
        }
        //从path的最后开始遍历
        int a=path.length-1;    //最后一行(背包容量)
        int b=path[0].length-1;   //最后一列(商品个数)
        while (a>0 && b>0){
            if(path[a][b]==1){
                System.out.println("将第"+a+"个商品放入背包");   //将第k和商品放入背包
                b-=w[a-1];  //将背包容量减去当如这个商品的重量
            }
            //商品数量-1
            a--;
        }
    }
}
